\contentsline {chapter}{\chapternumberline {1}Introduction}{1}{chapter.1}
\contentsline {paragraph}{Contributions.}{5}{section*.7}
\contentsline {paragraph}{State of the Art.}{5}{section*.8}
\contentsline {paragraph}{Organization.}{6}{section*.9}
\contentsline {chapter}{\chapternumberline {2}Existing Normal Forms For Relational Data}{7}{chapter.2}
\contentsline {section}{\numberline {2.1}Preliminaries}{7}{section.2.1}
\contentsline {section}{\numberline {2.2}Data Dependencies}{8}{section.2.2}
\contentsline {subsection}{\numberline {2.2.1}Functional Dependencies}{8}{subsection.2.2.1}
\contentsline {subsubsection}{\numberline {2.2.1.1}Implication of FDs}{9}{subsubsection.2.2.1.1}
\contentsline {subsubsection}{\numberline {2.2.1.2}Axiomatization for FDs}{9}{subsubsection.2.2.1.2}
\contentsline {section}{\numberline {2.3}Normal Forms}{10}{section.2.3}
\contentsline {subsection}{\numberline {2.3.1}Third Normal Form}{11}{subsection.2.3.1}
\contentsline {subsection}{\numberline {2.3.2}Boyce-Codd Normal Form}{11}{subsection.2.3.2}
\contentsline {section}{\numberline {2.4}Summary}{13}{section.2.4}
\contentsline {chapter}{\chapternumberline {3}Existing Normal Form For XML Data}{15}{chapter.3}
\contentsline {paragraph}{XML Documents.}{15}{section*.14}
\contentsline {paragraph}{Document Type Definitions (DTDs).}{16}{section*.16}
\contentsline {section}{\numberline {3.1}Preliminaries}{16}{section.3.1}
\contentsline {section}{\numberline {3.2}A Direct-Mapping From Relational Data To XML Documents}{22}{section.3.2}
\contentsline {section}{\numberline {3.3}Data Dependencies}{22}{section.3.3}
\contentsline {subsection}{\numberline {3.3.1}Tree Tuples}{23}{subsection.3.3.1}
\contentsline {subsection}{\numberline {3.3.2}XML Functional Dependencies}{25}{subsection.3.3.2}
\contentsline {subsubsection}{\numberline {3.3.2.1}Implication of XFDs}{26}{subsubsection.3.3.2.1}
\contentsline {paragraph}{Simple DTDs.}{27}{section*.22}
\contentsline {paragraph}{Relational DTDs.}{27}{section*.23}
\contentsline {subsubsection}{\numberline {3.3.2.2}Nonaxiomatizability of XFDs}{27}{subsubsection.3.3.2.2}
\contentsline {subsubsection}{\numberline {3.3.2.3}The Direct-Mapping of XFDs}{28}{subsubsection.3.3.2.3}
\contentsline {section}{\numberline {3.4}Normal Forms}{28}{section.3.4}
\contentsline {subsection}{\numberline {3.4.1}Redundancy in XML Documents}{29}{subsection.3.4.1}
\contentsline {subsection}{\numberline {3.4.2}XML Normal Form}{29}{subsection.3.4.2}
\contentsline {paragraph}{The Complexity of Testing XNF.}{34}{section*.28}
\contentsline {section}{\numberline {3.5}Summary}{34}{section.3.5}
\contentsline {chapter}{\chapternumberline {4}A New Normal Form For Description Logics}{37}{chapter.4}
\contentsline {section}{\numberline {4.1}Preliminaries}{38}{section.4.1}
\contentsline {subsection}{\numberline {4.1.1}The Description Logic $\textit {DL-Lite}_\mathcal {A}$}{38}{subsection.4.1.1}
\contentsline {subsubsection}{\numberline {4.1.1.1}Syntax of $\textit {DL-Lite}_\mathcal {A}$}{39}{subsubsection.4.1.1.1}
\contentsline {subsubsection}{\numberline {4.1.1.2}Semantics of $\textit {DL-Lite}_\mathcal {A}$}{42}{subsubsection.4.1.1.2}
\contentsline {subsubsection}{\numberline {4.1.1.3}Queries over $\textit {DL-Lite}_\mathcal {A}$ KB}{44}{subsubsection.4.1.1.3}
\contentsline {subsubsection}{\numberline {4.1.1.4}Reasoning in $\textit {DL-Lite}_\mathcal {A}$}{45}{subsubsection.4.1.1.4}
\contentsline {subsection}{\numberline {4.1.2}Reasoning over $\textit {DL-Lite}_\mathcal {A}$ KB}{46}{subsection.4.1.2}
\contentsline {subsection}{\numberline {4.1.3}Universal Model}{49}{subsection.4.1.3}
\contentsline {subsection}{\numberline {4.1.4}Query Answering over finite interpretations}{50}{subsection.4.1.4}
\contentsline {subsection}{\numberline {4.1.5}Query Answering over infinite interpretations}{52}{subsection.4.1.5}
\contentsline {subsubsection}{\numberline {4.1.5.1}Query Reformulation}{52}{subsubsection.4.1.5.1}
\contentsline {subsection}{\numberline {4.1.6}Additional Notions}{54}{subsection.4.1.6}
\contentsline {section}{\numberline {4.2}A Direct Mapping of Relational Data to Description Logic Knowledge Bases}{55}{section.4.2}
\contentsline {subsection}{\numberline {4.2.1}A Direct Mapping of Relational Data to RDF}{55}{subsection.4.2.1}
\contentsline {paragraph}{Fundamental properties}{57}{section*.34}
\contentsline {paragraph}{Desirable properties}{57}{section*.35}
\contentsline {subsection}{\numberline {4.2.2}A Direct Mapping of Relational Data to $\textit {DL-Lite}_\mathcal {A}$ Knowledge Bases}{59}{subsection.4.2.2}
\contentsline {section}{\numberline {4.3}Data Dependencies}{67}{section.4.3}
\contentsline {subsection}{\numberline {4.3.1}Path-based identification constraints}{67}{subsection.4.3.1}
\contentsline {subsubsection}{\numberline {4.3.1.1}KB satisfiability with pIdCs}{69}{subsubsection.4.3.1.1}
\contentsline {subsubsection}{\numberline {4.3.1.2}Implication of pIdCs}{70}{subsubsection.4.3.1.2}
\contentsline {subsubsection}{\numberline {4.3.1.3}Path-based IdCs as a formalism to model functional dependencies in $\textit {DL-Lite}_\mathcal {A}$}{74}{subsubsection.4.3.1.3}
\contentsline {subsection}{\numberline {4.3.2}FDs and pIdCs are semantically different}{74}{subsection.4.3.2}
\contentsline {subsection}{\numberline {4.3.3}Tree-based identification constraints}{78}{subsection.4.3.3}
\contentsline {subsubsection}{\numberline {4.3.3.1}KB satisfiability with tIdCs}{80}{subsubsection.4.3.3.1}
\contentsline {subsubsection}{\numberline {4.3.3.2}Implication of tIdCs}{81}{subsubsection.4.3.3.2}
\contentsline {subsubsection}{\numberline {4.3.3.3}The Direct-Mapping of FDs to IdCs}{82}{subsubsection.4.3.3.3}
\contentsline {section}{\numberline {4.4}Normal Forms}{84}{section.4.4}
\contentsline {subsection}{\numberline {4.4.1}Redundancy in $\textit {DL-Lite}_{\mathcal {A},tid}$ KBs}{84}{subsection.4.4.1}
\contentsline {subsection}{\numberline {4.4.2}$\textit {DL-Lite}_{\mathcal {A},tid}$ Normal Form}{85}{subsection.4.4.2}
\contentsline {section}{\numberline {4.5}BCNF - DLNF}{88}{section.4.5}
\contentsline {section}{\numberline {4.6}Summary}{90}{section.4.6}
\contentsline {chapter}{\chapternumberline {5}Conclusion}{93}{chapter.5}
\contentsline {section}{\numberline {5.1}Discussion}{93}{section.5.1}
\contentsline {section}{\numberline {5.2}Future Work}{94}{section.5.2}
\contentsline {chapter}{Bibliography}{95}{section*.52}
